#include <cstdio>
#include <cstdlib>


void eulerSieve(int n) 
{
    // 创建标记数组并初始化
    bool* isPrime = (bool*)malloc((n + 1) * sizeof(bool));
    int* primes = (int*)malloc(n * sizeof(int)); // 存储素数
    int count = 0; // 素数计数
    
    // 初始化标记数组，全部设为true
    for (int i = 2; i <= n; i++) 
	{
        isPrime[i] = true;
    }
    
    // 欧拉筛核心算法
    for (int i = 2; i <= n; i++) 
	{
        if (isPrime[i]) 
		{
            primes[count++] = i; // 记录素数
        }
        
        // 用当前已知的素数标记合数
        for (int j = 0; j < count && i * primes[j] <= n; j++) 
		{
            isPrime[i * primes[j]] = false;
            if (i % primes[j] == 0) 
			{
                break; // 关键步骤：确保每个合数只被标记一次
            }
        }
    }
    
    // 输出结果
    printf("2到%d之间的素数有：\n", n);
    for (int i = 0; i < count; i++) 
	{
        printf("%d ", primes[i]);
        if ((i + 1) % 10 == 0) printf("\n"); // 每10个素数换行
    }
    printf("\n共%d个素数\n", count);
    
    // 释放内存
    free(isPrime);
    free(primes);
}

int main() 
{
    int n;
    printf("请输入上限n: ");
    scanf("%d", &n);
    
    if (n < 2) 
	{
        printf("没有素数\n");
        return 0;
    }
    
    eulerSieve(n);
    return 0;
}